package com.jiang.剑指Offer.树.NC191;

import com.jiang.剑指Offer.树.TreeNode;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/09 17:29
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // 空树找不到公共祖先
        if (root == null) return -1;

        // p、q在该节点两边或某个等于说明这就是最近公共祖先
        if ((p < root.val && q > root.val) || (p > root.val && q < root.val) || p == root.val || q == root.val) {
            return root.val;
        } else if (p < root.val && q < root.val) { // p、q都在该节点的左边
            return lowestCommonAncestor(root.left, p, q);
        } else { // p、q都在该节点的右边
            return lowestCommonAncestor(root.right, p, q);
        }
    }
}